package leetcode.editor.cn;
/**
 * 两数之和
 */

import java.util.HashMap;
import java.util.Map;

public class TwoSum{
    public static void main(String[] args) {
        Solution solution = new TwoSum().new Solution();
        /**
         * 像这种有两个item有某种关系的算法题
         * 1.暴力求解--双重for循环
         * 2.使用HashTable来存储其中一个item,利用其关系只需要使用一重for循环
         */
    }
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                int temp = nums[i]+nums[j];
                if (temp==target) {
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

}